import heapq


# class Solution(object):
#     def nthUglyNumber(self, n):
#         """
#         :type n: int
#         :rtype: int
#         """
#         count = 0
#         s = {1}
#         stack = [1]
#         while True:
#             node = heapq.heappop(stack)
#             count += 1
#             if count == n:
#                 return node
#             else:
#                 if 2 * node not in s:
#                     s.add(2 * node)
#                     heapq.heappush(stack, 2 * node)
#                 if 3 * node not in s:
#                     s.add(3 * node)
#                     heapq.heappush(stack, 3 * node)
#                 if 5 * node not in s:
#                     s.add(5 * node)
#                     heapq.heappush(stack, 5 * node)


class Solution(object):
    def nthUglyNumber(self, n):
        """
        :type n: int
        :rtype: int
        """
        out = [0] * n
        out[0] = 1
        p0 = 0
        p1 = 0
        p2 = 0
        for i in range(1, n):
            num1 = out[p0] * 2
            num2 = out[p1] * 3
            num3 = out[p2] * 5
            out[i] = min(num1, num2, num3)
            if out[i] == num1:
                p0 += 1
            if out[i] == num2:
                p1 += 1
            if out[i] == num3:
                p2 += 1
        return out[-1]



data = Solution()
n = 10
print(data.nthUglyNumber(n))
